/*public class Test {

    public static int KMP(String str, String sub, int pos) {
        if (str == null || sub == null) return -1;
        int lenStr = str.length();
        int lenSub = sub.length();
        if (lenStr == 0 || lenSub == 0) return -1;
        if(pos < 0 || pos >= lenSub) return -1;

        int[] next = new int[lenSub];
        getNext(sub,next);

        int i = pos;
        int j = 0;

        while(i < lenStr && j < lenSub) {
            //j=-1 说明一开始就匹配失败了
            if(j == -1 || str.charAt(i) == sub.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if(j >= lenSub) {
            return i - j;
        }
        return -1;
    }

    public static void getNext(String sub,int[] next) {
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int k = 0;
        for (; i < sub.length(); ) {
            if(k == -1 || sub.charAt(i-1) == sub.charAt(k)) {
                next[i] = k+1;
                k++;
                i++;
            } else {
                k = next[k];
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(KMP("abababcd","abc", 0));
        System.out.println(KMP("ababcd","abc", 0));
        System.out.println(KMP("abababcd","ab", 0));
        System.out.println(KMP("abaccbabcd","accb", 0));
    }

}*/


public class Test {
    public static int KMP(String str, String sub, int pos) {
        if (str == null || sub == null) return -1;
        int lenStr = str.length();
        int lenSub = sub.length();
        if (lenStr <= 0 || lenSub < 0 || pos > lenStr) return -1;

        int[] next = new int[lenSub];
        getNext(next, sub);

        int i = pos;
        int j = 0;
        while (i < lenStr && j < lenSub) {
            if (j == -1 || str.charAt(i) == sub.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j >= lenSub) {
            return i - j;
        }
        return -1;
    }

    public static void getNext(int[] next, String sub) {
        int len = sub.length();
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int k = 0;
        while (i < len) {
            if (k == -1 || sub.charAt(i - 1) == sub.charAt(k)) {
                next[i] = k + 1;
                i++;
                k++;
            } else {
                k = next[k];
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(KMP("abcabccd", "abcc", 0));
        System.out.println(KMP("abcabccd", "abc", 0));
        System.out.println(KMP("abcabccd", "bc", 0));
    }
}



















